from typing import List
from collections import deque


class Solution:
    def connect(self, x: str, y: str) -> bool:
        diff = 0
        for i in range(len(x)):
            if x[i] == y[i]:
                continue
            diff += 1
        return diff == 1

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        queue = deque()
        visited = set()

        queue.append((beginWord, 0))
        visited.add(beginWord)

        while queue:
            node, steps = queue.popleft()
            if node == endWord:
                return steps + 1

            for i in wordList:
                if i in visited:
                    continue
                if self.connect(node, i):
                    queue.append((i, steps + 1))
                    visited.add(i)

        return 0
